1. Field of the Invention (Technical Field):
The present invention relates to apparatuses and methods for determining the median of a data set, particularly for image processing applications.
2. Background Art
The median of a data set is the value for which there are an equal number of values within the set which are smaller or equal as there are values which are larger or equal. Although there are a number of elegant solutions, the most common method of determining the median utilized is by sorting the set from largest to smallest and then choosing the middle value of the data set. Such methods when implemented to execute as quickly as possible require a large number of gates in a hardware implementation.
A primary advantage of the present invention is that the median is calculated through the use of simple adders, and therefore does not require re-registration of the input data set. In fact, as will be shown, the median can be determined utilizing a fully combinatorial logic solution to produce the output result. This results in a highly optimizable logic solution for Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC) implementation. Additionally, since the arithmetic median is a calculated value, it is unaffected by the ambiguities created when the data set includes large subsets of equivalent values occurring at or near the median value.
The present invention is particularly useful for real-time image processing applications, such as infrared image processing. For example, the invention is useful in local-area gain control applications which are useful in infrared image processing in environments with high temperature contrasts, such as between earth and sky. Communication data processing is another area of application for real-time median determination.
Since development of DC coupled infrared sensors, there has been a marked need to perform real-time two-dimensional median operations as part of dynamic range compression. Heretofore, massive FPGA and ASIC gate assets have been required to determine the median of 3×3, 5×5, and 7×7 image areas. This is because classic compare and swap solutions require a large network of N×(N−1)/2 comparators (or the recursive equivalent) to locate the median of N input values Prior arithmetic solutions required an N input adder network followed by a comparator circuit to determine the bit serial solution. This was more efficient for larger input sets but the concatenation of the adder and comparator introduces timing problems in higher clock rate systems. Anticipated detector geometries suggest much larger area median value determinations than 7×7 will be needed in the near future.
An example of an arithmetic solution requiring a comparator is presented by Law, “A Real-Time Radix-2-Based Median Filtering Algorithm”, IEEE 1991 Mid. Symp. Circuits and Systems, pp. 1121–24 (1992). Law identifies, on a bit by bit basis, the median value by adding all of the 2N weighted input values together and then determines the majority of the input values (which, by definition, is the 2N weighted median value).
The present invention eliminates the need for a concatenated comparator stage by introducing a constant K into the adder network. K is determined such that a singular 2M−1 output from the adder network represents the majority determination and therefore the median value